#include <iostream>
#include <vector>
#include <algorithm>
#include <ranges>
using namespace std;

class Solution {
	int min_cost(vector<int> &cuts, int l, int r)
	{
		if (l > r) {
			return 0;
		}
		int cost = INT32_MAX;
		for (int p = l; p <= r; p++) {
			cost = min(cost, cuts[r + 1] - cuts[l - 1] + min_cost(cuts, l, p - 1) + min_cost(cuts, p + 1, r));
		}
		return cost;
	}

	int min_cost(vector<int> &cuts)
	{
		int n = cuts.size() - 1;
		vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));

		for (int col = 1; col < n; col++) {
			for (int l = 1, r = col; r < n; l++, r++) {
                                dp[l][r] = INT32_MAX;
				for (int p = l; p <= r; p++) {
					dp[l][r] = min(dp[l][r], dp[l][p - 1] + dp[p + 1][r]);
				}
                                dp[l][r] += cuts[r + 1] - cuts[l - 1];
			}
		}
		return dp[1][n - 1];
	}

    public:
	int minCost(int n, vector<int> &cuts)
	{
		cuts.push_back(0);
		cuts.push_back(n);
		sort(cuts.begin(), cuts.end());
		//return min_cost(cuts, 1, cuts.size() - 2);
		return min_cost(cuts);
	}
};

int main()
{
	int n = 7;
	vector<int> cuts = { 1, 3, 4, 5 };
	cout << Solution().minCost(n, cuts) << endl;
	return 0;
}